/*
 * @lc app=leetcode.cn id=2516 lang=golang
 *
 * [2516] 每种字符至少取 K 个
 */
package Solutions

// @lc code=start
func takeCharacters(s string, k int) int {
	if k == 0 {
		return 0
	}
	la, lb, lc := 0, 0, 0
	ra, rb, rc := 0, 0, 0
	var check = func() bool {
		return (la+ra) >= k && (lb+rb) >= k && (lc+rc) >= k
	}
	for i := range s {
		if s[i] == 'a' {
			la++
		} else if s[i] == 'b' {
			lb++
		} else {
			lc++
		}
	}
	minStep := len(s) + 1
	if check() {
		minStep = len(s) - 1
	}
	for left, right := len(s)-2, 0; left >= -1; left-- {
		last := s[left+1]
		if last == 'a' {
			la--
		} else if last == 'b' {
			lb--
		} else {
			lc--
		}
		if check() {
			if left+right < minStep {
				minStep = right + left

			}
			continue
		}
		for right++; len(s)-right >= 0; right++ {
			if s[len(s)-right] == 'a' {
				ra++
			} else if s[len(s)-right] == 'b' {
				rb++
			} else {
				rc++
			}
			if s[len(s)-right] == last {
				break
			}
		}
	}
	if minStep == len(s)+1 {
		return -1
	}
	return minStep + 1

}

// @lc code=end
